Aller au contenu principal

Qu’est-ce que la complexité mémoire ?

Définition​

La complexité mémoire d’un algorithme mesure la quantité de mémoire supplémentaire (autre que les données d’entrée) que l’algorithme a besoin d’utiliser pour fonctionner.

En d'autres mots, combien d’espace en mémoire ton algorithme consomme pendant son exécution.

Exemple concret​

Imaginons ce code :

int[] tableau = {5, 3, 9, 1};
int somme = 0;

for (int i = 0; i < tableau.length; i++) {
    somme += tableau[i];
}

Complexité mémoire ?​

  • Le tableau est donné : on ne le compte pas.
  • La seule mémoire supplémentaire utilisée est la variable somme → donc la complexité mémoire est O(1) (constante).

Et si on utilisait un nouveau tableau ?​

int[] tableau = {5, 3, 9, 1};
int[] copie = new int[tableau.length];

for (int i = 0; i < tableau.length; i++) {
    copie[i] = tableau[i];
}

Ici, on crée un nouveau tableau de la même taille → la complexité mémoire est maintenant O(n), où n est la taille du tableau d’entrée.

Notation en grand O (Big O)​

Complexité mémoireSignification
O(1)Constante : très peu de mémoire utilisée
O(n)Linéaire : dépend de la taille des données
O(n²)Quadratique : doublement rapide de la mémoire selon les données

En résumé​

  • La complexité mémoire mesure la mémoire supplémentaire utilisée.
  • Elle est importante si :
    • Tu travailles avec beaucoup de données (ex. gros fichiers, image, IA, etc.)
    • Tu as des ressources limitées (ex. systèmes embarqués, téléphones)
  • On cherche souvent à avoir O(1) ou O(n), selon le contexte.

Algorithme en place (in-place)​

Un algorithme est dit en place (ou in-place en anglais) lorsqu'il effectue son travail directement dans la structure de données d'origine, sans créer de copie ni de tableau supplémentaire.

En termes de complexité mémoire, un algorithme en place utilise O(1) mémoire supplémentaire — c'est-à-dire seulement quelques variables temporaires (compteurs, index, valeur d'échange), quel que soit le nombre d'éléments à traiter.

Exemple : algorithme en place vs non en place​

// EN PLACE — O(1) mémoire supplémentaire
// On échange les valeurs directement dans le tableau original
int temp = tableau[i];
tableau[i] = tableau[j];
tableau[j] = temp;
// NON EN PLACE — O(n) mémoire supplémentaire
// On crée un nouveau tableau de la même taille
int[] copie = new int[tableau.length];
for (int i = 0; i < tableau.length; i++) {
    copie[i] = tableau[i];
}

À retenir : si un algorithme est décrit comme "en place" ou "in-place", cela signifie automatiquement que sa complexité mémoire est O(1).

Complexité mémoire des tris non récursifs​

Tous les algorithmes de tri étudiés dans ce cours sont en place (in-place) : ils trient le tableau d'origine sans créer de tableau supplémentaire.

AlgorithmeMémoire supplémentaireExplication
Tri à bullesO(1)Seulement une variable temporaire pour l'échange
Tri par sélectionO(1)Seulement l'index du minimum trouvé
Tri par insertionO(1)Seulement la valeur courante à insérer
Tri par tas (Heap Sort)O(1)Réorganise le tableau en place

Pourquoi c'est important ?​

Pour un tableau de 1 million d'entiers (≈ 4 Mo), un algorithme en place reste à O(1) de mémoire extra, quelle que soit la taille.

// Tri par sélection : O(1) mémoire supplémentaire
public static void triSelection(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        // Seule la variable temporaire `temp` est utilisée → O(1)
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

Règle à retenir : tous les tris non récursifs vus dans ce cours utilisent O(1) de mémoire supplémentaire — ils sont tous en place.

Complexité mémoire des streams (programmation parallèle)​

Lorsqu'on utilise des streams (ex. Stream en Java, PLINQ en C#), la mémoire supplémentaire est souvent O(n) de façon intrinsèque, même si on ne crée pas explicitement un nouveau tableau.

Pourquoi ?​

Les opérations de stream ne modifient pas la structure d'origine — elles produisent un nouveau flux de résultats. En pratique, les données sont souvent dupliquées ou tamponnées en mémoire :

  • Les opérations intermédiaires (map, filter, sorted) peuvent créer des copies intermédiaires.
  • En mode parallèle, le travail est divisé entre plusieurs threads : chaque portion de données est copiée dans des buffers séparés pour traitement concurrent.
  • Le résultat final est généralement collecté dans une nouvelle structure (collect()), ce qui double l'espace.

Exemple​

int[] tableau = {5, 3, 9, 1, 7};

// Stream parallèle : O(n) mémoire intrinsèque
int[] resultat = Arrays.stream(tableau)
    .parallel()
    .map(x -> x * 2)
    .toArray();
// → Les données originales + les données transformées coexistent en mémoire
ApprocheComplexité mémoireRemarque
Boucle for en placeO(1)Modifie le tableau original
Stream séquentielO(n)Crée un nouveau flux de résultats
Stream parallèleO(n)Buffers par thread + résultat final

À retenir : utiliser un stream (surtout parallèle) est souvent plus lisible et plus rapide en temps, mais cela a un coût mémoire de O(n) quasi systématique. Ce n'est pas nécessairement un problème, mais il faut en être conscient.